package ch4.part5;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * 桶排序，稳定排序，解决计数排序不能适用于浮点数的问题
 * <p>
 * 平均时间复杂度：O(n) = n
 * 最坏时间复杂度：O(n) = nlogn
 * 空间复杂度：O(n) = n
 *
 * @author liuwanxiang
 * @version 2019/06/15
 */
public class BucketSort {

    private static double[] sort(double[] array) {

        // 1. 循环数组，得最大值和最小值
        // 2. 构建与原数组等长的桶数组
        double min = 0.0, max = 0.0;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<>();
        for (double value : array) {
            if (value > max) {
                max = value;
            }
            if (value < min) {
                min = value;
            }
            bucketList.add(new LinkedList<>());
        }
        double length = max - min;
        int len = array.length;

        // 3. 遍历原数组，数据置入相应的桶内
        for (double value : array) {
            int bucketIndex = (int) ((value - min) * (len - 1) / length);
            bucketList.get(bucketIndex).add(value);
        }

        // 4. 桶内部进行排序
        for (LinkedList<Double> bucket : bucketList) {
            Collections.sort(bucket);
        }

        // 5. 构建有序数组
        double[] sortedArray = new double[len];
        int index = 0;
        for (int i = 0; i < len; i++) {
            LinkedList<Double> bucket = bucketList.get(i);
            if (!bucket.isEmpty()) {
                for (double value : bucket) {
                    sortedArray[index++] = value;
                }
            }
        }
        return sortedArray;

    }

    public static void main(String[] args) {
        double[] array = {5.1, 3.3, 6.3, 8.2, 0.9};
        double[] sortedArray = sort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

}
